package 二叉树;


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class TreeBasicOperation {
    // 前序遍历
    void preOrderTraversal(TreeNode root){
        if (root == null){
            return;
        }

        System.out.printf("%c", root.val);
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);
    }
    // 中序遍历
    void inOrderTraversal(TreeNode root){
        if (root == null){
            return;
        }
        inOrderTraversal(root.left);
        System.out.printf("%c", root.val);
        inOrderTraversal(root.right);
    }
        // 后序遍历
    void postOrderTraversal(TreeNode root){
        if (root == null){
            return;
        }
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.printf("%c", root.val);
    }

    //层序遍历
    ArrayList<ArrayList<Integer> > LevelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (root == null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()){
            ArrayList<Integer> list = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
                list.add(node.val);
            }
            res.add(list);
        }
        return res;
    }

    // 遍历思路-求结点个数
    static int size = 0;
    void getSize1(TreeNode root){
        if (root != null){
            size++;
            getSize1(root.left);
            getSize1(root.right);
        }
    }
    // 子问题思路-求结点个数
    int getSize2(TreeNode root){
        if (root != null){
            int leftSize = getSize2(root.left);
            int rightSize = getSize2(root.right);

            return 1 + leftSize + rightSize;
        }
        return 0;
    }
    // 遍历思路-求叶子结点个数
static int leafSize = 0;
void getLeafSize1(TreeNode root){
    if (root == null){
        return;
    }
    if (root.left == null && root.right == null){
        leafSize++;
    }
    getLeafSize1(root.left);
    getLeafSize1(root.right);
}
    // 子问题思路-求叶子结点个数
    int getLeafSize2(TreeNode root){
        if (root == null){
            return 0;
        }
        if (root.left == null && root.right == null){
            return 1;
        }
        int leftLeafSize = getLeafSize2(root.left);
        int rightLeafSize = getLeafSize2(root.right);
        return leftLeafSize + rightLeafSize;
    }
    // 子问题思路-求第 k 层结点个数
int getLevelSize(TreeNode root, int k){
    if (root == null){
        return 0;
    }
    if (k == 1){
        return 1;
    }
    int left = getLevelSize(root.left, k - 1);
    int right = getLevelSize(root.right, k - 1);
    return left + right;
}
    // 获取二叉树的高度
int getHeight(TreeNode root){
    if (root == null){
        return 0;
    }
    int left = getHeight(root.left);
    int right = getHeight(root.right);

    int m = Math.max(left, right);
    return m + 1;
}
    // 查找 val 所在结点，没有找到返回 NULL
    // 按照 根 -> 左子树 -> 右子树的顺序进行查找
    // 一旦找到，立即返回，不需要继续在其他位置查找
TreeNode find(TreeNode root, int val){
    if (root == null){
        return null;
    }
    if (root.val == val){
        return root;
    }

    TreeNode r = find(root.left, val);
    if (r != null){
        return r;
    }
    return find(root.right, val);
}
}
